package com.cxq.sort;

import java.util.Arrays;

public class SortCollection {
    //1 冒泡排序
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        int temp = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    //2 选择排序
    public static void selectSort(int[] arr) {
        int len = arr.length;
        int minIndex = 0, temp = 0;
        //外层循环只需要循环到倒数第二个数
        for (int i = 0; i < len - 1; i++) {
            minIndex = i;
            //内层循环必须要循环到最后一个数
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) minIndex = j;
            }
            if (minIndex == i) continue;
            else {
                temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    //3 插入排序
    //    一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
    //    从第一个元素开始，该元素可以认为已经被排序；
    //    取出下一个元素，在已经排序的元素序列中从后向前扫描；
    //    如果该元素（已排序）大于新元素，将该元素移到下一位置；
    //    重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
    //    将新元素插入到该位置后；
    //    重复步骤2~5。
    public static void insertSort(int[] arr) {
        int len = arr.length;
        int preIndex = 0, current = 0;
        for (int i = 1; i < len; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        System.out.println(Arrays.toString(arr));
    }

    //4 希尔排序(插入排序增强版)
    public static void shellSort(int[] arr) {
        int len = arr.length;
        //遍历所有的的步长
        for (int d = len / 2; d > 0; d /= 2) {
            //遍历所有元素
            for (int i = d; i < len; i++) {
                //遍历本组所有的元素
                for (int j = i - d; j >= 0; j -= d) {
                    //如果当前元素大于加上步长后的那个元素
                    if (arr[j] > arr[j + d]) {
                        int temp = arr[j];
                        arr[j] = arr[j + d];
                        arr[j + d] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        int len = arr.length;

    }


    public static void main(String[] args) {
        int[] arr = new int[]{7, 8, 5, 2, 1, 0, 4, 3, 9, 6};
//        bubbleSort(arr);
//        selectSort(arr);
//        insertSort(arr);
//        shellSort(arr);


        for (int i = 1; i < arr.length; i++) {
            int preIndex = i - 1;
            int cur = arr[preIndex + 1];
            while (preIndex >= 0 && arr[preIndex] > cur) {
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = cur;
        }
        System.out.println(Arrays.toString(arr));
    }
}
